import java.util.Arrays;
import java.util.Random;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 九转苍翎
 * Date: 2025/9/10
 * Time: 21:46
 */
public class Solution {
//    public int[] sortArray(int[] nums) {
//        quickSort(nums, 0, nums.length - 1);
//        return nums;
//    }
//    public void quickSort(int[] nums, int low, int high) {
//        if (low >= high) return;
//        int key = nums[new Random().nextInt(high - low + 1) + low],left = low - 1,right = high + 1,index = low;
//        while (index < right) {
//            if (nums[index] < key) {
//                swap(nums, ++left, index++);
//            }else if (nums[index] == key) {
//                index++;
//            }else {
//                swap(nums, --right, index);
//            }
//        }
//        quickSort(nums, low, left);
//        quickSort(nums, right, high);
//    }
//    public void swap(int[] nums, int i, int j) {
//       int temp = nums[i];
//       nums[i] = nums[j];
//       nums[j] = temp;
//    }
//    public static void main(String[] args) {
//        Solution solution = new Solution();
//        int[] ret = solution.sortArray(new int[]{6, 4, 7, 89, 3, 2, 1, 10});
//        System.out.println(Arrays.toString(ret));
//    }
    private int[] temp;
    public int[] sortArray(int[] nums) {
        temp = new int[nums.length];
        mergeSort(nums,0,nums.length - 1);
        return nums;
    }
    public void mergeSort(int[] nums,int left,int right) {
        if (left >= right) return;
        //1.根据中间点划分区间
        int middle = (left + right) / 2;
        //2.两个区间分别排序
        mergeSort(nums,left,middle);
        mergeSort(nums,middle + 1,right);
        //3.合并区间
        int cur1 = left,cur2 = middle + 1,index = 0;
        while (cur1 <= middle && cur2 <= right) {
            temp[index++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];
        }
        while (cur1 <= middle) {
            temp[index++] = nums[cur1++];
        }
        while (cur2 <= right) {
            temp[index++] = nums[cur2++];
        }
        //4.还原
        for (int i = left; i <= right; i++) {
            nums[i] = temp[i - left];
        }
    }
    public static void main(String[] args) {
        int[] nums = new int[]{23,5,7,2,78,21,9,123,62,1};
        Solution solution = new Solution();
        nums = solution.sortArray(nums);
        System.out.println(Arrays.toString(nums));
    }
}